package 双指针;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 统计优美子数组.java
 * @Description TODO
 * @createTime 2020年10月17日 16:13:00
 * 给你一个整数数组 nums 和一个整数 k。
 *
 * 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
 *
 * 请返回这个数组中「优美子数组」的数目。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2,1,1], k = 3
 * 输出：2
 * 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
 *
 * 思路：以k个奇数作为分割 分别统计奇数前面和后面的偶数的个数 统计完加到m上
 *      在移动前指针
 */
public class 统计优美子数组 {
    public static void main(String[] args) {
        int[] nums={1,1,2,1,1};
        int k=3;
//        int left = 0, right = 0, oddCnt = 0, res = 0;
//        while (right < nums.length) {
//            if ((nums[right++] & 1) == 1) {
//                oddCnt++;
//            }
//
//            if (oddCnt == k) {
//                 int tmp = right;
//                while (right < nums.length && (nums[right] & 1) == 0) {
//                    right++;
//                }
//                int rightEvenCnt = right - tmp;
//                 int leftEvenCnt = 0;
//                while ((nums[left] & 1) == 0) {
//                    leftEvenCnt++;
//                    left++;
//                }
//                  res += (leftEvenCnt + 1) * (rightEvenCnt + 1);
//
//                left++;
//                oddCnt--;
//            }
//
//        }
//
//        System.out.println(res);

//
//
//        class Solution {
//            public int numberOfSubarrays(int[] nums, int k) {
//                if (nums == null || nums.length == 0 || nums.length < k) return 0;
//                // 双指针
//                int left = 0, right = 0;
//                int count = 0; // 连续子数组中奇数的个数
//                int res = 0;
//                int preEven = 0; // 记录第一个奇数前面的偶数个数
//                while (right < nums.length){
//                    // 连续子数组中奇数个数不够
//                    if (count < k){
//                        if (nums[right] % 2 != 0) count++;
//                        right++; // 移动右侧指针
//                    }
//                    // 连续子数组中奇数个数够了，看第一个奇数前面有多少个偶数
//                    if (count == k) {
//                        preEven = 0;
//                        while (count == k){
//                            res++;
//                            if (nums[left] % 2 != 0) count--;
//                            left++;
//                            preEven++;
//                        }
//                    } else res += preEven; // 每次遇到 right 为偶数的时候就进行累加 相当于区间前面偶数个数 * 后面偶数个数
//                }
//                return res;
//            }
//        }

        int left=0,right=0;
        //count表示要返回的   temp表示当前奇数的个数
        int count=0,temp=0;
        for(;right<nums.length;right++){
            if(nums[right]%2==1){
                temp++;
            }
            //当窗口中有k个数的时候
            if(temp==k){
             //寻找到下一个奇数之前有多少个偶数  或者数组结束
             int right1=right;
                right1++;
             while(right1 < nums.length && (nums[right1] & 1) == 0){
                 right1++;
             }
             //sum表示窗尾有多少偶数
                int sum=right1-right-1;
             int sum2=0;
             while (nums[left]%2==0){
                 left++;
                 sum2++;
             }
             count+=(sum+1)*(sum2+1);
             left++;
             temp--;
            }
        }
        System.out.println(count);
    }
}
